package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: shm
 * @dateTime: 2020/10/5 20:04
 * @description: 15. 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * <p>
 * <p>
 * 示例：
 * <p>
 * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * <p>
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 */
public class ThreeSum {
    /**
     * @author: shm
     * @dateTime: 2020/10/5 20:17
     * @description: 方法一：排序 + 双指针
     * 我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2)O(N
     * 2
     * ) 减少至 O(N)O(N)。为什么是 O(N)O(N) 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的 bb），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)O(N)。
     * <p>
     * 注意到我们的伪代码中还有第一重循环，时间复杂度为 O(N)O(N)，因此枚举的总时间复杂度为 O(N^2)O(N
     * 2
     * )。由于排序的时间复杂度为 O(N \log N)O(NlogN)，在渐进意义下小于前者，因此算法的总时间复杂度为 O(N^2)O(N
     * 2
     * )。
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(N^2)O(N
     * 2
     * )，其中 NN 是数组 \textit{nums}nums 的长度。
     * <p>
     * 空间复杂度：O(\log N)O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(\log N)O(logN)。然而我们修改了输入的数组 \textit{nums}nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 \textit{nums}nums 的副本并进行排序，空间复杂度为 O(N)O(N)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int length = nums.length;
        if (length < 3) {
            return ans;
        }
        Arrays.sort(nums);
        for (int i = 0; i < length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            if (nums[i] + nums[length - 2] + nums[length - 1] < 0) {
                continue;
            }
            int left = i + 1, right = length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right - 1] == nums[right]) {
                        right--;
                    }
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return ans;
    }
}
